The present invention relates to routing data packets in heterogeneous networks and, in one aspect, to a method for routing Open Systems Interconnect (OSI) data packets over Internet Protocol (IP) networks.
As persons skilled in the art will appreciate, many conventional data networks, such as, for example, Synchronous Optical Network (SONET) or Synchronous Digital Hierarchy (SDH) networks, use the OSI protocol to enable communication between network elements.
In an OSI network there are four significant architectural entities: hosts (also known as End Systems), areas, backbones, and domains. A domain is any portion of an OSI network that is under common administrative authority and is similar in concept to an IP Autonomous System (AS). Within any OSI domain, one or more areas can be defined. An area is a logical entity; it is formed by a set of contiguous routers and the data links that connect them. All routers in the same area exchange information about all of the hosts that they can reach.
Areas are connected by level 2 routers (described below) which together form a backbone of the domain. All routers on the backbone know how to reach all areas. The term end system (ES) refers to any non-routing host or node; intermediate system (IS) refers to a router. These terms are the basis for the OSI End System-to-Intermediate System (ES-IS) (described in ISO 9543, available from the International Organization for Standardization (ISO) at www.iso.ch, the contents of which are hereby incorporated herein by reference) and Intermediate System-to-Intermediate System (IS-IS) (described in ISO 10589, xe2x80x9cIntermediate system to Intermediate system intra-domain routing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode Network Service (ISO 8473)xe2x80x9d also available from the ISO, the contents of which are hereby incorporated herein by reference) protocols.
Routing can be divided into two categories or levels: level 1 routing refers to intra-area routing; while level 2 routing refers to inter-area routing. An IS (i.e., a router) that can only perform intra-area routing is referred to as a level 1 IS. Similarly, an IS capable of inter-area (or intra-domain) routing is considered to be a level 2 IS.
As a result of their functionality, a level 1 IS need only be aware about the level 1 ISs and ESs within its area and the nearest level 2 IS should a packet received by a level 1 IS require inter-area routing. In contrast, a level 2 IS must be aware of the topology of the area it serves (i.e., the level 1 ISs and ESs in the area); the other level 2 ISs within its domain; and how to reach all other areas within its domain.
IS-IS routing is the standard intra-domain (i.e., inter-area) routing protocol in the OSI protocol suite. The IS-IS routing protocol, being a link state protocol, requires each IS running the IS-IS protocol to determine (e.g., xe2x80x9cmeetxe2x80x9d) each of its neighbors and assess the state of each link between itself and its neighbors. This information is stored in a link state circuit table which is used to generate Link State Advertisements or Packets (LSPs) which are transmitted or flooded across the network to each IS. A circuit identifies a logical connection or channel over which communication can occur. LSPs are transmitted whenever an IS determines that there has been change in a link between itself and a neighboring IS. For example, an IS transmits LSPs when it is determined that a link has failed or changed with respect to the link""s cost metric (hereinafter xe2x80x9ccostsxe2x80x9d), or when a new neighbor is discovered. Only those routers which are directly connected to each other can form an adjacency and become xe2x80x9cnearest neighboursxe2x80x9d (i.e. neighboring routers must be directly adjacent to each other and share a common data link).
On receipt of these LSPs, an IS is able to determine a complete picture of the domain topology and compute optimal routes to each ES in the domain. The routing algorithm used by IS-IS is the Shortest Path First (SPF) algorithm.
Other information is also included in the LSPs transmitted and received by the ISs. For example, LSPs also include costs associated with the use of each link. As a result, costs associated with the optimal routes can also be calculated. Further, LSPs include sequence number and remaining lifetime fields which are used to determine if a duplicate LSP has been received, whether the link information is too old, etc.
While OSI compliant networks are popular and quite common, the use of IP networks has proliferated and continues to gain in popularity. As a result, there is a need to enable the co-existence of these two networking protocols. Accordingly, a protocol (often referred to in the art as xe2x80x9cIntegrated IS-ISxe2x80x9d) has been developed to enable routers to support both the IS-IS and IP routing protocols. Integrated IS-IS (described in Request For Comment (RFC) 1195, available from the Internet Engineering Task Force (IETF) and available at www.ietf.org, the contents of which are hereby incorporated herein by reference) provides for the routing of IP packets by simply using existing IS-IS packets with the addition of IP-specific fields. Accordingly, each IS router need only run the OSI Integrated IS-IS routing protocol to provide for the routing of IP packets. Use of Integrated IS-IS routing protocol has been reasonably successful in the past in addressing the needs of heterogeneous networks which have been comprised of predominately OSI network elements (i.e., elements transmitting OSI-compliant packets) with small numbers of IP network elements.
However, the relatively recent widespread adoption of IP networking technology has resulted in heterogeneous networks which have, to a larger extent than previous, relatively large numbers of IP network elements. This increase in IP network elements combined with an increase in the number of IP packets being transmitted (and, thus, requiring routing) has demonstrated that the use of Integrated IS-IS in these heterogeneous networks is somewhat inefficient. For example, Integrated IS-IS, while providing the routing protocol, does not provide the forwarding functionality. This results in each protocol stack still being responsible for the forwarding of packets. IP routing using Integrated IS-IS routers is also limited to those IP sub-networks which are contained within a single OSI area. If multicasting capability is desired, Integrated IS-IS requires a router to run a separate multicasting protocol which results in further overhead and degradation of performance. Moreover, many data transmissions require exterior routing (i.e., routing between domains) which, in the Integrated IS-IS protocol, is simply not as well developed as IP exterior routing. Further, it has been noted that Integrated IS-IS does not scale well due to L2 router connectivity requirements.
Other attempted solutions to provide OSI and IP routing run software implementing the complete OSI and IP routing protocols completely independently from one another (often referred to as the Ships In the Night (SIN) method). However, this method has not been satisfactory due to the increased computational overhead required to run two separate and independent protocols.
Accordingly, providing a manner for the routing of data packets in heterogeneous networks which addresses these shortcomings is desirable.
Advantageously, embodiments of the present provide improved routing of data packets in heterogeneous networks especially in networks that comprise network elements transmitting predominately IP messages. Specifically, routers embodying aspects of the present invention may, in some instances, run software implementing portions of the OSI routing protocol and software implementing the IP routing protocol simultaneously. Moreover, these embodiments provide for the exchange of routing information between software implementing these two protocols.
In one embodiment, routers initially run only the IP routing protocol and a router will only commence simultaneous use of the OSI routing protocols if, and when, the router receives an OSI routing protocol data packet (e.g., an ES-IS Helloxe2x80x94ESHxe2x80x94or IS-IS Helloxe2x80x94ISH) or other OSI trigger. On receipt of an OSI trigger, the router determines, using other aspects of the present invention, its nearest OSI neighbours using the IP routing table. Whenever there is a change in the IP routing table or, if desired, after a specified time out period, a router running the OSI routing protocol may re-determine its nearest neighbours. As only those routers receiving OSI routing packets need run the OSI routing protocols, there is no need for the increased overhead associated with running Integrated IS-IS at each router in the domain.
Moreover, some embodiments of the present invention may, after failing to receive OSI packets for a period of time, cease running the OSI routing protocol. These embodiments result in only those routers xe2x80x9cactivelyxe2x80x9d receiving OSI packets running software implementing both the OSI routing and IP protocols with the remaining routers running only the IP routing protocols. Embodiments of the invention provide advantages (e.g., lower overhead) when compared to the SIN method. Further, aspects of the invention are not limited to interior routing only, as is the case with Integrated IS-IS.
In one aspect of the invention there is provided a method for routing data packets complying with a first or a second routing protocol over a heterogeneous network complying in part with said second routing protocol, the method comprising: if a packet received complies with said first routing protocol, determining, according to said first routing protocol, a destination on said heterogeneous network; and routing said packet received to said destination on said heterogeneous network, said routing using said second routing protocol.
In a further aspect of the invention there is provided an Internet Protocol (IP) router forming part of a heterogeneous network formed, in part, by an IP network, said IP router adapted to: receive a packet conforming with one of Internet Protocol and a different protocol; if said packet received conforms with said different protocol, temporarily running said different protocol to determine routing for said packet received; and routing said packet over said IP network responsive to said routing determined whenever there is no end-to-end route through said heterogeneous network complying with said different protocol.
In a further aspect of the invention there is provided a method for routing a packet according to first routing protocol over a heterogeneous network using a second routing protocol, said method comprising: receiving said packet; running said first routing protocol; determining a route for said packet received using said first routing protocol and said second routing protocol; routing said packet received over said heterogeneous network according to said route determined; and ceasing said running of said first routing protocol.
In a further aspect of the invention there is provided a method for routing Open Systems Interconnect (OSI) compliant packets over an Internet Protocol (IP) data network with an IP router, said method comprising: temporarily running OSI routing protocol on said IP router; determining a route for said OSI compliant packets using IP routing information; and transmitting said OSI compliant packets over said IP data network in accordance with said route determined.
In a further aspect of the invention there is provided a computer readable media containing instructions to adapt an Internet Protocol (IP) router to: on receipt of Open Systems Interconnect (OSI) compliant packets, temporarily operate OSI routing protocol on said IP router; determine a route for said OSI compliant packets using IP routing information; and transmitting said OSI compliant packets over said IP data network in accordance with said route determined.
In a further aspect of the invention there is provided a method of identifying a first router""s nearest neighbouring routers from a plurality of routers, the first router and the plurality of routers forming part of a packet switched data network, said method comprising: transmitting a request over said packet switched data network to at least some of said plurality of routers; for each of said some of said plurality of routers receiving said request: determining whether said request was received over said packet switched data network on an optimal route; and if said request was received over said packet switched data network on an optimal route then transmitting a response to said request to said first router identifying said router transmitting said response as a nearest neighbouring router to said first router.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.